from typing import *


class Solution:

    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:
        f = [-1] * (target + 1)
        nums.sort()
        f[0] = 0
        for num in nums:
            for i in range(target, -1, -1):
                if f[i] != -1 and i + num <= target:
                    f[i + num] = max(f[i + num], f[i] + 1)
        return f[target]


s = Solution()
print(s.lengthOfLongestSubsequence(nums=[1, 2, 3, 4, 5], target=9))
